package com.yaoli.base;

/**
 * Created by YaoLi on 2017/8/21.
 *
 * 为什么归并排序不如 快速排序 和 堆排序
 *
 * 因为归并排序在 合并数组的 时候需要另外一个 重新申请 一个空间
 *
 * 而申请空间本身就需要花费大量时间。
 *
 * 但是归并排序的好处就是有序的。
 */
public class GuiBinPaiXu {
    public static void main(String[] args) {
        GuiBinPaiXu g = new GuiBinPaiXu();
        int array [] =  {5 ,23,34,2,32,12,1,12,4,23,245,13};
        int result [] = new int[array.length];

        g.sort(array,0,array.length - 1,result);
        System.out.println("");
    }


    // length = 10;
    // (0 + 10 - 1) / 2 = 4
    // 0 1 2 3 4             5 6 7 8 9
    // length = 9
    // (0 + 9 - 1) / 2 = 4
    // 0 1 2 3 4             5 6 7 8
    public void sort(int array [] ,int begin ,int end ,int [] result){



        if(begin >= end){
            return;
        }else{

            int m = (begin + end - 1) / 2;
            sort(array,begin,m ,result);
            sort(array,m + 1,end, result);
            calc(array,begin,m,m+1,end,result);

        }
    }


    public void calc(int [] array,int a1,int a2,int b1,int b2,int result[]){

        // {12,23,34,1,21,                33,2,32,5,75,43};
        int p1 = a1;
        int p2 = b1;

        int p = a1;

        while(p1 <= a2 && p2 <= b2){

            if(array[p1] < array[p2]){
                result[p] = array[p1];
                p1++;
            }else{ // array[a1] >= array[a2]
                result[p] = array[p2];
                p2++;
            }
            p++;

        }

        if(p1 <= a2){
            for(int i = p1 ; i <= a2 ; i++,p++){
                result[p] = array[i];
            }
        }
        if(p2 <= b2){
            for(int i = p2 ; i <= b2 ; i++,p++) {
                result[p] = array[i];
            }
        }

        for (int i = a1 ; i <= b2 ; i++) {
            array[i] = result[i];
        }

    }
}
